2-2

a.
To complete correctness, we have to claim the set $\{A^{'}[1], A^{'}[2], ... , A^{'}[n]\}$ is exactly equal to $\{A[1], A[2], ... , A[n]\}$. That is, $A^{'}[1, ...,n]$ consists of the elements originally in $A[1, ...,n]$. It's not difficult to observe since the only modified operation inside nested loop is swapping elements, that guarantees our claim.

b.
Loop Invariant (for-loop of line 2~4):
At the start of each for-loop iteration, $A[j] \leq A[k]$ for all $j \leq k \leq A.length$. $(*)$

Initialization:
In the first iteration of for-loop, we have $j = A.length$, and that $A[j] \leq A[k]$ for all $A.length \leq k \leq A.length$ is clear.

Maintenance:
Suppose $(*)$ is true for some $j$. If $A[j-1] \leq A[j]$ doesn't hold, the swapping operation will make the inequality hold through swapping $A[j]$ and $A[j-1]$. Therefore $(*)$ holds for $j-1$ after this iteration.

Termination:
When the for-loop terminates, we have $j=i+1$ and $(*)$ holds for $j-1$ after the final iteration. Hence, $A[i] \leq A[k]$ for all $i \leq k \leq A.length$.

c.
Loop Invariant (for-loop of line 1~4):
At the start of each for-loop iteration, the elements in $A[1,...,i-1]$ are in sorted order and all less than any element in $A[i,...,A.length]$. $(**)$

Initialization:
In the first iteration of for-loop, we have $i=1$. Then $(**)$ holds obviously because $A[1,...,i-1]$ is empty.

Maintenance:
Suppose $(**)$ is true for some i. The inner for-loop provides that $A[i] \leq A[k]$ for all $i \leq k \leq A.length$, so we have $A[l] \leq A[i] \leq A[k]$ for all $l$ in $[1,...i-1]$ and $k$ in $[i,...,A.length]$. And, note that $A[1,...,i-1]$ is in sorted order and unmodified during this iteration, it concludes $(**)$ holds for $i+1$.

Termination:
When the for-loop terminates, we have $i=A.length-1$ and $(**)$ holds for $i+1$ after the final iteration. Hence, $A[1,...,A.length-1]$ is sorted and less than $A[A.length]$, thus $A[1,...,A.length]$ is sorted. This completes correctness of (2.3).

d.
Let $n=A.length$, $t_i$ denote the iterating times of inner for-loop for given $i$, and $T(n)$ denote the running time of BUBBLESORT. Consider the following analysis:

BUBBLESORT(A)	cost	time
for i = 1 to A.length-1	$c_1$	$n-1$
for j = A.length downto i+1	$c_2$	$\sum^{n-1}_{i=1}{t_i}$
if A[j] < A[j-1]	$c_3$	$\sum^{n-1}_{i=1}{t_i}$
exchange A[j] with A[j-1]	$c_4$	$\sum^{n-1}_{i=1}{t_i}$

By observation, $t_i=n-i$ and then $$T(n) = c_1(n-1)+c_2\sum^{n-1}_{i=1}{t_i}+c_3\sum^{n-1}_{i=1}{t_i}+c_4\sum^{n-1}_{i=1}{t_i}=c_1(n-1)+(c_2+c_3+c_4)\sum^{n-1}_{i=1}{t_i}=c_1(n-1)+(c_2+c_3+c_4)\frac{n(n-1)}{2}$$ Thus, the worst-case running time of BUBBLESORT is $c_1(n-1)+(c_2+c_3+c_4)\frac{n(n-1)}{2}$.
Note that both the best and worst running time of BUBBLESORT is $\Theta(n)$. ($\because \frac{c_2+c_3+c_4}{2}n^2 \leq T(n) \leq (c_1+c_2+c_3+c_4)n^2$ $\therefore T(n) = \Theta(n)$) Now we have the same complexity of worst-case running time of bubble sort and insertion sort. But insertion sort has best-case running time complexity of $\Theta(n)$, which is better than bubble sort's best-case running time complexity of $\Theta(n)$.

3-2

A	B	O	o	$\Omega$	$\omega$	$\Theta$
$\lg^{k}n$	$n^{\epsilon}$	yes	yes	no	no	no
$n^k$	$c^n$	yes	yes	no	no	no
$\sqrt{n}$	$n^{\sin{n}}$	no	no	no	no	no
$2^n$	$2^{\frac{n}{2}}$	no	no	yes	yes	no
$n^{\lg c}$	$c^{\lg n}$	yes	no	yes	no	yes
$\lg{(n!)}$	$\lg{(n^n)}$	yes	no	yes	no	yes

3-3

a.
Let $f \simeq g$ if $f = \Theta(g)$. Note that $\simeq$ is an equivalence relation. And let $f \succ g$ denote the relation $f = \Omega(g)$.
Then we have $2^{2^{n+1}}$ $\succ$ $2^{2^n}$ $\succ$ $(n+1)!$ $\succ$ $n!$ $\succ$ $(\lg{n})!$ $\succ$ $e^n$ $\succ$ $n \cdot 2^n$ $\succ$ $2^n$ $\succ$ $(\frac{3}{2})^n$ $\succ$ $n^{\lg{\lg{n}}}$ $\simeq$ $(\lg n)^{\lg n}$ $\succ$ $n^3$ $\succ$ $n^2$ $\simeq$ $4^{\lg n}$ $\succ$ $\lg(n!)$ $\simeq$ $n \lg n$ $\succ$ $2^{\lg{n}}$ $\simeq$ $n$ $\succ$ $(\sqrt{2})^{\lg{n}}$ $\succ$ $2^{\sqrt{2 \lg n}}$ $\succ$ $\lg^2{n}$ $\succ$ $\ln{n}$ $\succ$ $\sqrt{\lg n}$ $\succ$ $\ln \ln n$ $\succ$ $2^{\lg^{*}{n}}$ $\succ$ $\lg^{*}{n}$ $\simeq$ $\lg^{*}{(\lg n)}$ $\succ$ $\lg{(\lg^{*}{n})}$ $\succ$ $n^{\frac{1}{\lg{n}}}$ $\simeq$ $1$.

b.
$e^{\tan{\frac{n\pi}{4}}}$

3-4

a. False b. False c. True d. False  e. False f. True g. False h. False 

A counterexample of d.
Let $f(n)=n$, $g(n)=\frac{n}{2}$, then we have $0 \leq n \leq 2 \frac{n}{2}$ for all $n \in \mathbb{N}$, therefore $f(n)=O(g(n))$. But for any constant $c \in \mathbb{R}$, the limit $$\lim_{n \rightarrow \infty}{\frac{c2^{\frac{n}{2}}}{2^n}}=0$$ implies that $2^n \neq O(2^{\frac{n}{2}})$.